#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode
{
    int val;
    struct ListNode*next ;
} ListNode;


void out_put(ListNode*head)
{
    if (!head)
    {
        return ;
    }

    ListNode*    temp    =    head;
    while (temp) // i++ ++i
    {
        printf("%d\n",temp->val);
        temp = temp->next;
    }
}

ListNode* create_list(int arr[],int n)
{
    // 0 == n
    if (0 == n)
    {
        return NULL;
    }

    // 定义哑节点
    ListNode*dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy ->next = NULL;
    ListNode*temp = dummy;
    

    for (int i = 0;i < n;i++)
    {
        ListNode*node = (ListNode*)malloc(sizeof(ListNode));
        node->val = arr[i];
        node->next = NULL;

        temp->next = node;
        temp = node;
    }

    return dummy->next;
}

ListNode* delete_node(ListNode*head,int target)
{
    ListNode*dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->next = head;

    // 查找删除
    ListNode*temp = head;
    ListNode*prev = dummy;
    while (temp)
    {
        if (target == temp->val)
        {
            // 找到
            prev->next = temp->next;
            free(temp);
            temp = NULL;
            break;
        }
        prev = prev->next;
        temp = temp->next;
    }

    return dummy->next;
}

ListNode*insert_node(ListNode*head,int data)
{
    ListNode*node = (ListNode*)malloc(sizeof(ListNode));
    node->val = data;
    node->next = NULL;

    ListNode*dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->next = head;

    ListNode*temp = dummy;
    while (temp)
    {
        if (data<=temp->next->val&&data>=temp->val)
        {
            ListNode*n = temp->next;
            temp->next = node;
            node->next = n;
            break;
        }
        temp = temp->next;
    }

    // temp到最后了
    if (!temp)
    {
        temp = node;
    }

    return dummy->next;
}

int compare(void *pa,void *pb)
{
    return (*(int*)pa)<(*(int*)pb);
}

ListNode*sort_node(ListNode*head)
{
    int len = 0;
    ListNode*temp = head;
    while (temp)
    {
        len++;
        temp = temp->next;
    }

    int arr[len];
    temp = head;
    int i = 0;
    while (temp)
    {
        arr[i] = temp->val;
        i++;
        temp = temp ->next;
    }

    // qsort(arr,arr+len-1,sizeof(temp->val),comapre);

    temp = head;
    i = 0;
    while (temp)
    {
        temp->val = arr[i];
        i++;
        temp = temp->next;
    }

    return head;
}

int main()
{
    int arr[3] = {1,2,3};
    ListNode*head = create_list(arr,3);
    head = insert_node(head,2)  ;
    out_put(head);
    return 0;
}